package Java241210;
//给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始起点。如果两个链表不存在相交节点，返回null.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class One241210 {
    public ListNode getIntersectionNode(ListNode headA,ListNode headB){
        if (headA == null || headB == null){
            return null;
        }

        ListNode pl = headA;  //假设现在单链表A比单链表B长
        ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;
        while (pl != null){   //求单链表A长度
            lenA++;
            pl = pl.next;
        }
        pl = headA;  //不加这一句，pl此时就是null
        while (ps != null){   //求单链表B长度
            lenB++;
            ps = ps.next;
        }
        ps = headB;
        int len = lenA - lenB;  //差值步，先让最长的单链表走len步后，两链表再同时走

        if (len < 0){  //说明单链表A长度 < B
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }//此时，pl永远指向最长的链表，ps永远指向了最短的链表
        while (len != 0 ){   //pl走差值len步
            pl = pl.next;
            len--;
        }
        if ( pl != ps ){
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }
}
public class Main {
    public static void main(String[] args) {
        // 构建示例链表，这里你可以根据实际情况修改链表节点的值以及结构来测试不同场景
        ListNode headA = new ListNode(1);
        ListNode node2A = new ListNode(2);
        ListNode node3A = new ListNode(3);
        ListNode headB = new ListNode(4);
        ListNode node2B = new ListNode(5);
        ListNode commonNode = new ListNode(6);

        headA.next = node2A;
        node2A.next = node3A;
        node3A.next = commonNode;

        headB.next = node2B;
        node2B.next = commonNode;

        One241210 solution = new One241210();
        ListNode intersection = solution.getIntersectionNode(headA, headB);
        if (intersection!= null) {
            System.out.println("相交节点的值为: " + intersection.val);
        } else {
            System.out.println("链表无相交节点");
        }
    }
}
